package leetcode.array.sum;

import java.util.HashMap;
import java.util.Map;

/**
 * 560. 和为K的子数组个数
 *
 * 指定数组中和为 k的子数组的个数 (子数组必定是数组的连续部分)
 *
 */
public class SubarraySum {

    public static void main(String[] args) {
        SubarraySum subarraySum = new SubarraySum();
        // 示例数据
        int[] nums = {-1, 0, 1, 2, -1, -4, -2, -3, 3, 0, 4};

        // 开始时间
        long start = System.currentTimeMillis();

        int count = subarraySum.subarraySum0(nums, 1);
        System.out.println(count);

        // 结束时间
        long end = System.currentTimeMillis();
        System.out.println("花费时间(毫秒): " + (end - start));
    }


    /**
     * 和为 k 的子数组的个数
     *
     * 暴力破解 时间复杂度为 O(n^2)
     *
     * @param nums 数组
     * @param k    和的值
     * @return
     */
    public int subarraySum0(int[] nums, int k) {
        int count = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            int sum = 0;
            for (int j = i; j < n; j++) {
                sum = sum + nums[j];
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }


    /**
     * 前缀和 + 哈希表
     * 时间和空间复杂度均为O(n)
     */
    public int subarraySum(int[] nums, int k) {
        int n = nums.length;
        int count = 0;
        int pre = 0;
        // 建立哈希表 HashMap, 以前缀和为 key, 前缀和出现次数为 value,
        // 记录 pre[i]出现的次数, 从左往右边更新 HashMap边计算答案
        Map<Integer, Integer> map = new HashMap<>(n);
        map.put(0, 1);
        for (int i = 0; i < n; i++) {
            pre = pre + nums[i];
            int target = pre - k;
            // 如果HashMap包含 pre[i]−k的值, 取出次数计入总次数
            if (map.containsKey(target)) {
                count = count + map.get(target);
            }
            // 每一个元素的前缀和都需要保存到HashMap中, key重复的话 value更新为 +1
            map.put(pre, map.getOrDefault(pre, 0) + 1);
        }
        return count;
    }

}
